package leetcode.editor.cn.q1_300.q50;

import java.util.ArrayList;
import java.util.List;

/**
 * @author qidi
 * @date 2021-12-13 16:50:21
 */
class Q0068_TextJustification {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<String> fullJustify(String[] words, int maxWidth) {
            if (words == null || words.length == 0) return null;

            List<String> rows = new ArrayList<>();
            int size = 0;

            int l = 0;
            int r = 0;
            while (r < words.length) {
                if (size + words[r].length() + r - l - 1 >= maxWidth) {
                    StringBuilder row = new StringBuilder();

                    // 空格总长度
                    int spaceWith = maxWidth - size;
                    // 空格总数
                    int num = r - l - 1;
                    if (num == 0) {
                        // 说明只有一个单词
                        row.append(words[l]);
                        while (spaceWith > 0) {
                            row.append(' ');
                            spaceWith--;
                        }
                        l = r;
                    } else {
                        // 每个空格的长度
                        int w = spaceWith / num;
                        // 需要补充空格的数量
                        int rem = spaceWith % num;

                        while (l < r) {
                            row.append(words[l]);
                            if (l != r - 1) {
                                for (int i = 0; i < w + (rem > 0 ? 1 : 0); i++) {
                                    row.append(' ');
                                }
                                rem--;
                            }
                            l++;
                        }
                    }
                    rows.add(row.toString());
                    size = 0;
                } else {
                    size += words[r].length();
                    r++;
                }
            }

            StringBuilder row = new StringBuilder();
            // 最后一行需要左对齐
            while (l < r) {
                row.append(words[l]);
                l++;
                if (l == r) continue;
                row.append(' ');
            }

            while (maxWidth > row.length()) {
                row.append(' ');
            }

            rows.add(row.toString());
            return rows;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0068_TextJustification().new Solution();
        List<String> list;
        list = solution.fullJustify(new String[]{"ask", "not", "what", "your", "country", "can", "do", "for", "you", "ask", "what", "you", "can", "do", "for", "your", "country"}, 16);
//        list = solution.fullJustify(new String[]{"This", "is", "an", "example", "of", "text", "justification."}, 16);
        for (String s : list) {
            System.out.println(s);
        }
        System.out.println();
//
//        list = solution.fullJustify(new String[]{"What", "must", "be", "acknowledgment", "shall", "be"}, 16);
//        for (String s : list) {
//            System.out.println(s);
//        }
//        System.out.println();
//
//        list = solution.fullJustify(new String[]{"Science", "is", "what", "we", "understand", "well", "enough", "to", "explain", "to", "a", "computer.", "Art", "is", "everything", "else", "we", "do"}, 20);
//        for (String s : list) {
//            System.out.println(s);
//        }
//        System.out.println();
    }
}